Close

%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi/2016/07.20.11.13
%2 sid.inpe.br/sibgrapi/2016/07.20.11.13.39
%@doi 10.1109/SIBGRAPI.2016.015
%T Reducing the number of points on the convex hull calculation using the polar space subdivision in E2
%D 2016
%A Skala, Vaclav,
%A Smolik, Michal,
%A Majdisova, Zuzana,
%@affiliation University of West Bohemia
%@affiliation University of West Bohemia
%@affiliation University of West Bohemia
%E Aliaga, Daniel G.,
%E Davis, Larry S.,
%E Farias, Ricardo C.,
%E Fernandes, Leandro A. F.,
%E Gibson, Stuart J.,
%E Giraldi, Gilson A.,
%E Gois, João Paulo,
%E Maciel, Anderson,
%E Menotti, David,
%E Miranda, Paulo A. V.,
%E Musse, Soraia,
%E Namikawa, Laercio,
%E Pamplona, Mauricio,
%E Papa, João Paulo,
%E Santos, Jefersson dos,
%E Schwartz, William Robson,
%E Thomaz, Carlos E.,
%B Conference on Graphics, Patterns and Images, 29 (SIBGRAPI)
%C São José dos Campos, SP, Brazil
%8 4-7 Oct. 2016
%I IEEE Computer Society´s Conference Publishing Services
%J Los Alamitos
%S Proceedings
%K Convex hull, iterative approximation, space subdivision, reduction of points.
%X A convex hull of points in E2 is used in many applications. In spite of low computational complexity O(h log⁡n ) it takes considerable time if large data processing is needed. We present a new algorithm to speed up any planar convex hull calculation. It is based on a polar space subdivision and speed up known convex hull algorithms of 3,7 times and more. The algorithm estimates the central point using 10% of the data; this point is taken as the origin for the polar subdivision. The space subdivision enables a fast and very efficient reduction of the given points, which cannot contribute to the final convex hull. The proposed algorithm iteratively approximates the convex hull, leaving only a small number of points for the final processing, which is performed using a standard algorithm. Non-eliminated points are then processed by a selected standard convex hull algorithm. The algorithm is simple and easy to implement. Experiments proved numerical robustness as well.
%@language en
%3 ConvexHull [SIBGRAPI_2016].pdf


Close